#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
using namespace std;
/* #ifdef ONLINE_JUDGE */

/* #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) */
/* char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf; */

/* #endif */
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 1e5 + 5, M = 1e5 + 5, mod = 1e9 + 7;
string f[100];
char strbuf[N];
array <int, M> g1, g2, g3;
int main() {
	freopen("brotherhood.in", "r", stdin);
	freopen("brotherhood.out", "w", stdout);
	int n = read(), T = read();
	if (n <= 10) {
		f[1] = "0", f[2] = "1";
		for (int i = 3; i <= n; i++)
			f[i] = f[i - 1] + f[i - 2];
	}
	/* else { */
		g1[5] = g1[6] = 1;
		g1[7] = 3;
		for (int i = 8; i <= n; i++) {
			g1[i] = g1[i - 1] + g1[i - 2] + (i & 1);
			if (g1[i] >= mod) g1[i] -= mod;
		}
		g2[1] = g2[3] = g2[4] = 1;
		for (int i = 5; i <= n; i++) {
			g2[i] = g2[i - 1] + g2[i - 2];
			if (g2[i] >= mod) g2[i] -= mod;
		}
		g3[2] = g3[3] = 1;
		for (int i = 4; i <= n; i++) {
			g3[i] = g3[i - 1] + g3[i - 2];
			if (g3[i] >= mod) g3[i] -= mod;
		}
	/* } */
	/* for (int j = 1; j <= 12; j++) { */
		/* int ans = 0; */
		/* for (int i = 0; i < f[j].size(); i++) { */
			/* if (f[j][i] == '1' && f[j][i + 1] == '1') */
				/* ans++; */
			/* if (f[j][i] == '1') */
				/* ans++; */
		/* } */
		/* write(ans), putchar(32); */
		/* write(g1[j]), puts(""); */
		/* printf("%s\n", f[j].c_str()); */
	/* } */
	/* puts(""); */
	/* printf("%s\n", f[n].c_str()); */
	while (T--) {
		if (n <= 10) {
			scanf("%s", strbuf);
			string tmp = strbuf;
			int ans = 0;
			for (int i = 0; i < f[n].size(); i++) {
				bool flg = false;
				for (int j = 0; j < tmp.size(); j++) {
					if (f[n][i + j] == tmp[j]) continue;
					flg = 1;
					break;
				}
				ans += !flg;
			}
			write(ans), puts("");
		}
		else {
			scanf("%s", strbuf);
			string tmp = strbuf;
			if (tmp == "11")
				write(g1[n]), puts("");
			else if (tmp == "0")
				write(g2[n]), puts("");
			else if (tmp == "1")
				write(g3[n]), puts("");
			else
				write(0), puts("");
		}
	}
	return 0;
}
